#include "trees.h"
#include "tree-algorithms.h"
#include "dynamic-tree.h"
#include "simple-tree.h"
#include "simple-path.h"
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstdarg>

using namespace std;


template <class E>
Trees::Edge<E>::Edge(int v1, int v2, const E& value)
		: m_v1(v1), m_v2(v2), m_value(value) 
{
}

template <class E>
Trees::Edge<E>::Edge()
{
}

namespace Trees 
{
	template <class E>
	bool CompareEdges(const Edge<E>& e1, const Edge<E>& e2)
	{
		return e1.m_value < e2.m_value;
	}
}

template <class E>
istream& operator>>(istream &in, Trees::Edge<E> &edge)
{
	in >> edge.m_v1 >> edge.m_v2 >> edge.m_value;
}

template <class E>
Trees::Forest<E>::Forest(const size_t n_ver)
{
	n_vertices = n_ver;
	m_trees = NULL;
}

template <class E>
void Trees::Forest<E>::InitForest()
{
	if ( m_trees )
	{
		DeleteForest();
	}
	m_trees = new DynamicTree<int,EdgeInfo<E> >*[n_vertices];
	for (int i = 0; i < n_vertices; i++)
	{
		m_trees[i] = CreateTree(i);
	}
}

template <class E>
void Trees::Forest<E>::DeleteForest()
{
#ifdef TREE_DEBUG
	cerr << "DeleteForest() >>>" << endl;
#endif
	if ( m_trees )
	{
		for (int i = 0; i < n_vertices; i++)
		{
			delete m_trees[i];
		}
		delete [] m_trees;
		m_trees = NULL;
	}
#ifdef TREE_DEBUG
	cerr << "DeleteForest() <<<" << endl;
#endif
}

template <class E>
Trees::DynamicTree<int,Trees::EdgeInfo<E> >* Trees::Forest<E>::CreateTree(int value)
{
	return new SimpleTree<int,EdgeInfo<E> >(value);
}

template <class E>
Trees::PathForest<E>::PathForest(const size_t n_ver) : Forest<E>(n_ver), dotCount(0) {}

template <class E>
Trees::DynamicTree<int,Trees::EdgeInfo<E> >* Trees::PathForest<E>::CreateTree(int value)
{
	return new SimplePathTree<int,EdgeInfo<E> >(value, this);
}

template <class E>
Trees::Forest<E>::~Forest()
{
	DeleteForest();
}

template <class E>
void Trees::PathForest<E>::printDot(ostream& out, const char* fmt, ...)
{
	dotCount++;
	out << "digraph G" << dotCount << " {" << endl;
	out << "    graph [ rankdir=\"LR\" ];" << endl << endl;
	
	for (int i = 0; i < this->n_vertices; i++)
	{
		SimplePathTree<int,E>* t = dynamic_cast<SimplePathTree<int,E>* >(this->m_trees[i]);
		SimplePathTree<int,E>* after = t->m_after;
		SimplePathTree<int,E>* before = t->m_before;
		SimplePathTree<int,E>* dparent = dynamic_cast<SimplePathTree<int,E>* >(t->m_dParent);
		SimplePath<int,E>* path = t->m_path;
		
		cout << "    " << t->Value() << " [ label=\"<value> " << t->Value() 
				<< " | <before> " << ( before ? "m_before" : "" )
				<< " | <after> " << ( after ? "m_after" : "" )
				<< " | <dparent> " << ( dparent ? "m_dParent" : "" )
				<< " | <path> " << ( path ? "m_path" : "" )
				<< "\" shape=\"record\" ];" << endl;
				
		if ( before )
		{
			cout << "        " << t->Value() << ":before -> " << before->Value() << ":value [ color=\"black\" ];" << endl;
		}
		if ( after )
		{
			cout << "        " << t->Value() << ":after -> " << after->Value() << ":value [ color=\"black\" label=\"" << t->Cost() << "\"];" << endl;
		}
		if ( dparent )
		{
			cout << "        " << t->Value() << ":dparent -> " << dparent->Value() << ":value [ color=\"grey\" label=\"" << t->DCost() << "\" ];" << endl;
		}
		if ( path )
		{
		
			cout << "    Path_" << path->m_id << " [label=\"<name> Path_" << path->m_id
					<< " | <head> " << ( path->m_head ? "m_head" : "" )
					<< " | <tail> " << ( path->m_tail ? "m_tail" : "" )
					<< "\" shape=\"record\" ];" << endl;
					
			cout << "        " << t->Value() << ":path -> Path_" << path->m_id << ":name [ color=\"green\" ];" << endl;
			if ( path->m_head )
			{
				cout << "        Path_" << path->m_id << ":head -> " << path->m_head->Value() << ":value [color=\"blue\"];" << endl;
			}
			if ( path->m_tail )
			{
				cout << "        Path_" << path->m_id << ":tail -> " << path->m_tail->Value() << ":value [color=\"yellow\"];" << endl;
			}
		}
	}
	cout << endl;
	
	char buf[1024];
	va_list vl;
	va_start(vl, fmt);
	vsprintf(buf, fmt, vl);
	va_end(vl);
	
	cout << "    label=\"" << buf << "\";" << endl;
	
	out << "}" << endl;
}

template <class E>
const E Trees::Forest<E>::MinSpanningTreeMargin(vector<Trees::Edge<E> > edges)
{
	InitForest();
	sort(edges.begin(), edges.end(), CompareEdges<E>);
	
	typedef typename vector<Edge<E> >::iterator EdgeIterator;

#ifdef TREE_DEBUG
	printDot(cout, "Initial Forest");
#endif

	int size = 0;
	E minMargin = Trees::max_value<E>();
	list<EdgeInfo<E> > usedEdges;
	
	
	for (EdgeIterator itr = edges.begin(); itr != edges.end(); itr++)
	{
		typedef typename list<EdgeInfo<E> >::iterator EI;
		
		Edge<E>& edge = *itr;
		EdgeInfo<E> cost(edge.m_value);
		usedEdges.push_back(cost);
		EI back = usedEdges.end();
		back--;
		cost.edgeItr = back;
		
		DynamicTree<int,EdgeInfo<E> >* v = m_trees[edge.m_v1];
		DynamicTree<int,EdgeInfo<E> >* w = m_trees[edge.m_v2];

#ifdef TREE_DEBUG
		cerr << "Adding edge: " << edge.m_v1 << " -- " << edge.m_v2 << " : " << edge.m_value << endl;
#endif		
		v->Evert();
		if ( w->Root() == v )
		{
			// v and w are in the same tree
			DynamicTree<int,EdgeInfo<E> >* minCostNode = w->MinCost();
			EdgeInfo<E> minCost = minCostNode->Cost();
			if ( minCost < cost )
			{
				// remove least cost edge, and add new
#ifdef TREE_DEBUG
				cerr << "remove " << minCostNode->Value() << " -- " 
						<< minCostNode->Parent()->Value() << " : " << minCostNode->Cost() << endl;
#endif						
				minCostNode->Cut();
				usedEdges.erase(minCost.edgeItr);
#ifdef TREE_DEBUG
				cerr << "add " << w->Value() << " -- " << v->Value() << " : " << cost << endl;
#endif
				w->Link(v, cost);
			}
		}
		else
		{
			// v and w are from different trees
#ifdef TREE_DEBUG
			cerr << "add " << w->Value() << " -- " << v->Value() << " : " << cost << endl;
#endif			
			w->Link(v, cost);
			size++;
		}
#ifdef TREE_DEBUG
		cerr << "Added edge: " << edge.m_v1 << " -- " << edge.m_v2 << " : " << edge.m_value << endl;
#endif		
		
		if ( size == n_vertices - 1 )
		{
			//E minEdge = MinEdge();
			EdgeInfo<E> minEdge = usedEdges.front();
			E margin = cost.m_cost - minEdge.m_cost;
#ifdef TREE_DEBUG
			cerr << "Checking spanning tree: minEdge=" << minEdge << " margin=" << margin << endl;
#endif			
			if ( margin < minMargin )
			{
				minMargin = margin;
			}
		}
#ifdef TREE_DEBUG
		cerr << "Completed edge: " << edge.m_v1 << " -- " << edge.m_v2 << " : " << edge.m_value << endl;
		printDot(cout, "Edge: %d -- %d : %d", edge.m_v1, edge.m_v2, edge.m_value);
#endif
	}
	
	return minMargin;
}

template <class E>
const E Trees::Forest<E>::MinEdge() const
{
#ifdef TREE_DEBUG
	cerr << "Forest::MinEdge >>>" << endl;
#endif	
	E minCost = max_value<E>();
	for (int i = 0; i < n_vertices; i++)
	{
		DynamicTree<int, EdgeInfo<E> >* t = m_trees[i];
		if ( t->Parent() )
		{
			EdgeInfo<E> cost = t->Cost();
#ifdef TREE_DEBUG
			cerr << "Forest::MinEdge: " << t->Value() << " has parent " << t->Parent()->Value() << " and cost " << cost << endl;
#endif
			if ( cost.m_cost < minCost )
			{
				minCost = cost.m_cost;
			}
		}
#ifdef TREE_DEBUG
		else
		{
			cerr << "Forest::MinEdge: " << t->Value() << " has no parent" << endl;
		}
#endif		
	}
#ifdef TREE_DEBUG
	cerr << "Forest::MinEdge <<< return " << minCost << endl;
#endif	
	return minCost;
}

template class Trees::Edge<int>;

template class Trees::Forest<int>;

template class Trees::PathForest<int>;
